//
// Description: 896. 最长上升子序列 II
// Created by Loading on 2022/6/3.
//

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 10;

int a[N];
// q[i] 表示长度为 i 的上升子序列的末尾元素最小值
int q[N];

/*
 * 优化朴素 dp，基于贪心思想，q 储存每个长度上升子序列结尾最小元素，
 * 因为如果可以衔接更大的数后边，那么就一定能够衔接到更小的数后边，预留更大空间；
 * 遍历每个数时，二分查找当前数可以衔接到已求出的最长的上升子序列长度的后边，
 * 最终输出长度即可
 */
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // q 中元素的个数，即最长上升子序列的长度
    int len = 0;
    // q 一定为单调递增序列，第 0 个位置初始化为极小值
    q[0] = INT_MIN;
    for (int i = 0; i < n; ++i) {
        int l = 0, r = len;
        // 二分查找
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        // 更新最大长度
        len = max(len, l + 1);
        // 当前数插入 q 数组，一定为 l + 1 位置
        q[l + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}